There has been explosive growth in Internet traffic due to the increased number of Internet users, various service demands from those users, the implementation of new services, such as voice-over-IP (VoIP) or streaming applications, and the development of mobile Internet. Conventional routers, which act as relaying nodes connected to sub-networks or other routers, have accomplished their roles well, in situations in which the time required to process packets, determine their destinations, and forward the packets to the destinations is usually smaller than the transmission time on network paths. More recently, however, the packet transmission capabilities of high-bandwidth network paths and the increases in Internet traffic have combined to outpace the processing capacities of conventional routers.
This has led to the development of a new generation of massively parallel, distributed architecture routers. A distributed architecture router typically comprises a large number of routing nodes that are coupled to each other via a plurality of switch fabric modules and an optional crossbar switch. Each routing node has its own routing (or forwarding) table for forwarding data packets via other routing nodes to a destination address.
When a data packet arrives in a conventional routing node, a forwarding engine in the routing node uses forwarding tables to determine the destination of the data packet. A conventional Internet Protocol (IP) router uses a dedicated forwarding table for each type of traffic, such as Internet Protocol version 4 (IPv4), Internet Protocol version 6 (IPv6) and MPLS.
However, conventional routing tables have severe limitations. Using separate forwarding engines and forwarding processes with independent forwarding tables for each packet type is inefficient in terms of computing resources and memory utilization. It is desirable to eliminate separate lookup tables for each type of traffic, so that a single lookup (i.e., forwarding) table may forward mixed data packet types. Moreover, conventional routing tables are best suited for relatively lower speed routers (i.e., 100 Mbps or less) and for relatively small address sizes (i.e., 32 bits or less). It also is desirable to allow packet forwarding based on class of service (CoS) and/or higher layer protocols.
Performing an IPv6 forwarding table lookup at high-speed line rates (e.g., 10 Gbps) is a challenge because of the large address range (128-bit addresses). There currently is not a practical method for doing IPv6 lookups at line speed for high-speed interfaces (e.g., 10 Gbps routers). Current proposals use ternary content addressable memory (TCAM) devices to increase lookup speed, but doing the entire search in TCAM is not practical due to the expense and high power consumption of TCAM devices. Also, hashing and state of the art searching techniques are not adequate because it is necessary 1) to keep tables within a reasonable size limit for cost and performance considerations and 2) to keep the number of lookup stages low enough that memory access time does not prevent the lookup speeds from keeping up with line speeds.
The assignee of the present application has submitted three related patent applications directed to solving some of these problems. These three applications are: 1) U.S. patent application Ser. No. 10/431,770, entitled “Apparatus and Method for Combining Forwarding Tables in a Distributed Architecture Router,” filed on May 8, 2003, and currently pending; 2) U.S. patent application Ser. No. 10/665,192, entitled “Apparatus and Method for Classifying Traffic in a Distributed Architecture Router,” filed on Sep. 4, 2003, now U.S. Pat. No. 6,940,981; and 3) U.S. patent application Ser. No. 10/658,977, entitled “Apparatus and Method for Performing High-Speed Lookups in a Routing Table,” filed on Sep. 10, 2003, and currently pending; U.S. patent application Ser. Nos. 10/431,770, 10/665,192 and 10/658,977 are hereby incorporated by reference into the present application.
Each of these solves some of the problems of large forwarding table indices and large numbers of routes. U.S. patent application Ser. Nos. 10/431,770 and 10/665,192 are suitable for use in 1 Gbps routers and provide an adequate solution for line rates up to 1 Gbps. U.S. patent application Ser. No. 10/658,977 provides a solution for line rates up to 10 Gbps. The present application expands upon the ideas in U.S. patent application Ser. Nos. 10/431,770, 10/665,192 and 10/658,977.
U.S. patent application Ser. No. 10/431,770 solved the problems of dealing with three large tables and of the complexity of dealing with three separate forwarding tables for IPv4, IPv6, and Multiprotocol Label Switching (MPLS) by folding these into a single forwarding table. U.S. patent application Ser. No. 10/431,770 disclosed the use of address space sharing between IPv4 and MPLS and the tunneling of IPv6 data packets. A classification engine based on state graph technology was used to compress the IPv6 address into the address to be tunneled and a CAM was used to speed the lookup. The approach disclosed in U.S. patent application Ser. No. 10/431,770 differs from traditional uses of CAMs in that the classification engine allowed the fields in the lookup index to vary on a packet-by-packet basis determined by packet contents, instead of using fixed bit fields. However, the method disclosed in U.S. patent application Ser. No. 10/431,770 is less suitable for use in a 10 Gbps router, because classification engines are not available that operate at the 10 Gbps line rate.
U.S. patent application Ser. No. 10/665,192 extended the use of the classification engine to add new functionality to routers. U.S. patent application Ser. No. 10/665,192 disclosed the modification of the data packet in the forwarding process, thereby enabling the new functionality. The new functionality included: 1) providing security in the form of user anonymity by translating Layer 2 and Layer 3 addresses in the classification engine; 2) providing support for Network Address Translation (leading to configuration independence); and 3) enabling forwarding based on Layer 2 through Layer 7 information, instead of Layer 3 forwarding only. U.S. patent application Ser. No. 10/665,192 also provided support for content-based billing, firewall functionality, and data surveillance capabilities at the router core instead of at a host computer.
U.S. patent application Ser. No. 10/658,977 disclosed a new apparatus and method for forwarding IPv6 data packets at high-speed line rates (e.g., 10 Gbps). U.S. patent application Ser. No. 10/658,977 abandoned the use of classification engines because conventional classification engines cannot operate at 10 Gbps. U.S. patent application Ser. No. 10/658,977 expanded on the prior art by compacting the search tables to fit within practical SRAM sizes while allowing the final lookup stage to use DRAM, by combining the compacted search tables with pipelined hardware lookup support, and by including an initial CAM-based hashing technique into multiple trie trees to narrow the lookup width in the trie search.
However, the apparatus and method disclosed in U.S. patent application Ser. No. 10/658,977 are suitable for homogeneous packet types where the important fields do not change from packet to packet, but are less suitable for mixed data packet types, where the important fields change from packet to packet. The nature of the pipelining is such that each stage of the pipeline acts upon every packet. If a packet does not need the processing of a pipeline stage, then the resources of that pipeline stage are idle when the packet traverses that stage.
Therefore, there is a need in the art for an improved router that does not suffer from the above-described problems associated with the prior art. In particular, there is a need for a distributed router that is capable of forwarding mixed types of data packets at high-speed lines rates, such as 1 gigabits per second (Gbps) and higher. More particularly, there is a need for a distributed router that forwards mixed data packets at high line rates without using large amounts of content addressable memory (CAM). Still more particularly, there is a need for a distributed router that forwards mixed data packets at high line rates without using classification engines.